This application incorporates by reference Taiwanese application Serial No. 80105249, Filed Apr. 2, 1999.
1. Field of the Invention
This invention is related to a means for syndrome generation in a Video/Audio processing system, and more particularly to a generation means and a method for identifying the receiving code words in the compact disk (CD) decoding process.
2. Description of the Related Art
Syndrome generation is a checking process for identifying the receiving code words. The syndrome is generated by multiplying the receiving code words by the checking vectors. The equation of syndrome generation is given as follows:
S=xcexa3(Rixc3x97xcex1i),
wherein S represents the syndromes, Ri represents the code words, xcex1 represents the checking vector, which is a shift byte and i is the order. xcex1 is the element of a Galois Field, and the value of it is (00000010)b. Taking A, an element of the Galois Field, as an example, the product of A multiplied by xcex1i can be yielded by left shifting A by i bit, if i is not larger than 7. If i is larger than 7, the product of A multiplied by xcex1i can be generated by the following equation derived from the character of the Galois Field:
xcex18=xcex14⊕xcex13⊕xcex12⊕xcex10,
wherein xe2x80x9c⊕xe2x80x9d is an Exclusive OR (XOR) operator.
For any element of the Galois Field, A, as the Most Significant Bit (MSB) is 1, the product of A multiplied by xcex1 is the XOR operation result of (00011101)b and the value of A left-shifting one bit. On the other hand, as the MSB is not 1, the product of A multiplied by is the value of A after left shifting by one bit. This left-shifting and XOR operation are so-called shift operation, and therefore xcex1 is called a shift byte. Conventionally, as the mathematics characteristic of a Galois Field is applied in the multiplication performed by any software and hardware, table-matching or logic circuit including a large number of the gate counts is necessary.
It is sometimes possible that a compact disk (CD) may suffer from physical damage, for example, scratches, during production or use. To prevent logical continuous data from being lost as a result of the physical damage, a data scramble technique is typically employed during the data-write process of CD read-only-memory (CD-ROM) production. In short, each logical continuous data stream is first divided into a plurality of blocks according to a predetermined algorithm. Afterwards, another algorithm is employed to scramble blocks of one logical continuous data stream with blocks of other logical continuous data streams. The resulting scrambled data are then sequentially and continuously written into the physical spaces of the CD. When, unfortunately, a certain portion of the CD is damaged, the portion of damaged data belonging to one logical continuous data stream may be recovered by the associated un-damaged data of the respective logical continuous data stream via the algorithm. Therefore, in addition to the raw data, some extra data, including control code, sync code, and protection code are added to the raw data to form the complete data in the CD.
In order to prevent data damage or loss, when original data are to be stored in disks, the following encoding operations are sequentially performed: C3 encoding, C2 encoding, interleaving, and C1 encoding.
The interleaving operation re-partitions frames of C2 coded data into different frames for C1 coding. After interleaving, if data is damaged, the damaged data is dispersed among different frames of the decoded data, and thus correction probability is enhanced.
Therefore, when data in a disk is read, the following decoding operations are sequentially performed: C1 decoding, deinterleaving, C2 decoding, and C3 decoding. Deinterleaving is a reverse operation of interleaving.
During the process of writing data into the CD, encoding the C3 code, encoding the C2 code, interleaving codes and encoding the C1 code are the essential steps, wherein the C3 code is encoded by sectors, each sector has 98 frames and each frame has 24 bytes. The C2 code is encoded by frame. In the step of encoding the C2 code, each frame has an additional four parity check bytes beyond the 24 bytes output from the C3 code. The original 24 bytes and the additional 4 parity check bytes are yielded by the following equation:
xe2x80x83W3xc3x97G2=V2,
wherein W3 is the 24-byte code word matrix of C2 output from C3, which is a 1xc3x9724 matrix, G2 is a generating matrix, which is a 24xc3x9728 matrix, and V2 is the code word of the C2 code, which is a 1xc3x9728 matrix, and also the code word after the C2 code encoding step.
Similarly, the 28-byte code word of the C2 code is first processed through interleaving codes, then multiplied by a generating matrix G1 of the C1 code to yield a 32-byte code word V1. V1 is the code word after the C1 code encoding. The 32-byte code word V1 includes the above 28 bytes from the C2 code word and the other four bytes of the parity check code. Then, the data after encoding is written in the CD.
While the data is read from the CD, the read source code has to be decoded. The process of decoding includes sequentially the steps of decoding the C1 code, deinterleaving codes, decoding the C2 code, and decoding the C3 code. The steps of decoding the C1 code include multiplying the read 32-byte code word, which is a 1xc3x9732 matrix V1, by a 32xc3x974 checking matrix H1 to yield a 1xc3x974 syndromes matrix S. The equation is given as follows.
S=V1xc3x97H1=[S0S1S2S3],
wherein
S0=V0⊕V1⊕V2⊕31;
S1=V0⊕V1xcex1⊕V2xcex12⊕ . . . V31xcex131;
xe2x80x83S2=V0⊕V1xcex12⊕V2xcex14⊕ . . . V31xcex162; and
S3=V0⊕V1xcex13⊕V2xcex16⊕ . . . V31xcex193.
The yielded data are identified to be correct if the values of S0, S1, S2 and S3 are all equal to zero. If not, there must exist errors.
The processes of decoding the C2 code and the C3 code include also similar syndrome generation steps. It is therefore not further described herein.
The equation for generating the four syndromes can be represented as followed:
Sj=xcexa3R1xc3x97(xcex1i)j,
wherein, Ri represents the receiving code words R0, R1, R2, R3, . . . , and R31, i=0xcx9c31, and Sj represents the syndromes S0, S1, S2, and S3, j=0xcx9c3
Let (Sj)i=R0xc3x97(xcex10)j⊕R1xc3x97(xcex11)j⊕R2xc3x97(xcex12)j⊕ . . . ⊕Rixc3x97(xcex1i)j, wherein the syndrome (Sj)i is the result for generating recursively for i+1 times.
FIG. 1 is a block diagram of the conventional syndrome generating means. Referring to FIG. 1, the code word R0 is first written in the register 10, which is the syndrome (Sj)0. At the next timing, the code word R1 is multiplied by the checking vector (xcex11)j using a multiplier 12. The product yielded by the above-mentioned multiplication operation and the output value of the register 10 are then processed through an XOR operation by an XOR gate 14 to yield the syndrome (Sj)1, and then the syndrome (Sj)1 is fed back to the register 10. At the next timing, similar operation is performed to yield the syndrome (Sj)2. By such recursive operation, the finally yielded syndrome (Sj)31 is syndrome Sj.
For every multiplication operation, using the conventional syndrome generating means, table matching or complicate logic circuits have to be utilized. For a syndrome generation, a multiplication operation and an XOR operation are both necessary so that not only a large number of table matching steps have to be taken but also a great number of logic gates are used, which needs large memory capacity and extends the processing period.
It is therefore an object of the invention to provide a means and method for syndrome generation which makes use of a shift register and an XOR gate for decoding and generating the syndrome recursively. The means and method is used in the Video/Audio processing system, which rapidly and effectively accomplishes the syndrome generation. This invention has the advantages of simple structure, reducing significant operation time, and reducing the memory capacity.
It is therefore another object of the invention to provide a means for syndrome generation, which is able to accomplish the syndrome generation for a code word with a number of bytes. The means for syndrome generation includes an XOR gate and a register for receiving a shift byte of the bytes. Then, XOR operation is then performed to yield the syndrome.
It is therefore another object of the invention to propose a method for syndrome generation, which is used for generating the syndrome for a code word with a number of bytes. First, let one of the bytes be a register value. Next, an XOR operation of the register value, a shift byte and another one of the bytes is performed. The result of the XOR operation replaces the register value and the step is repeated until the syndrome generation is accomplished.